package com.test;

import java.util.*;

 class ListNode {
   int val;
  ListNode next = null;
   public ListNode(int val) {
    this.val = val;
  }
 }


public class test2 {
    public static void main(String[] args) {
        ListNode head = new ListNode(3);
        head.next = new ListNode(2);
        head.next.next = new ListNode(1);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(1);
        ListNode temp = new ListNode(0);
        temp = remove_duplicate(head);
        System.out.println(temp.val);
        System.out.println(temp.next.val);
        System.out.println(temp.next.next.val);
        System.out.println(temp.next.next.next.val);
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @return ListNode类
     */
    public static ListNode remove_duplicate (ListNode head) {
        // write code here
        if(head == null){
            return head;
        }
        ListNode tmp = head;
        Map<Integer,Integer> map = new HashMap<>();
        while(tmp != null){
            map.put(tmp.val, map.getOrDefault(tmp.val,0)+1);
            tmp = tmp.next;
        }
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode temp = dummy;
        Set<Integer> set = new HashSet<>();
        while(temp != null && temp.next != null){
            if(map.get(temp.next.val)>1){
                if(set.contains(temp.next.val)){
                    temp.next = temp.next.next;
                } else {
                    set.add(temp.next.val);
                }
            }
            temp = temp.next;
        }
        return dummy.next;
    }
}



